package analysis.lexicalAnalysis;

import domain.StatusInfo;
import utils.CommonUtils;

import java.util.*;

/**
 * NFA 转换为 DFA
 */
public class NfaToDfa {

    // 状态转化变量
    private String[] chList;

    private ArrayList<String> chArrayList;
    // 从左到右，第一个key代表行(转换前的状态)，
    // 第二个key代表列(状态转换的变量)，
    // 第二个value代表表项(转换后的状态)
    private Map<String, Map<String, ArrayList<String>>> statusMap;

    private Map<Set<String>, Map<String, Set<String>>> newStatusMap;

    private Map<String, Map<String, String>> newStatusMapSimplify;

    // 新旧状态映射表
    private Map<Set<String>, String> statusMapTable;

    // 开始状态
    private List<String> startStatus;

    //结束状态
    private List<String> endStatus;

    // 新的开始状态
    private List<String> newStartStatus;

    // 新的结束状态
    private List<String> newEndStatus;

    // 子集法中的状态集，用来记录是否有进行closure(move(T, a))
    private Map<Set<String>, Boolean> dStates;

    public NfaToDfa() { }

    public NfaToDfa(String[] chList, Map<String, Map<String, ArrayList<String>>> statusMap, List<String> startStatus, List<String> endStatus) {
        this.chList = chList;
        this.statusMap = statusMap;
        this.endStatus = endStatus;
        this.startStatus = startStatus;
        chArrayList = new ArrayList<>();
        chArrayList.addAll(Arrays.asList(chList));
    }

    /**
     * NFA转换成DFA
     */
    public StatusInfo nfaToDfa(){
        // 步骤1：ε-closure(S) 是dStates中的唯一状态，且未加标记
        // 将开始状态求一个ε-closure就是初始状态
        Set<String> S;
        if(chArrayList.contains("ε")){  // 如果状态转换表中包含ε，则进行ε的闭包计算，否则直接原始初态设置为现今的初态
            S = CommonUtils.closure(new HashSet<>(startStatus), statusMap);
        }else{
            S = new HashSet<>(startStatus);
        }
        dStates = new HashMap<>();
        newStatusMap = new HashMap<>();
        //初始状态，将其放入状态集中，并设为false
        dStates.put(S, false);
        while(dStates.containsValue(false)){
            Set<String> set = getKey();
            Map<String, Set<String>> statusChanged = new HashMap<>();
            for (String change : chList) {
                if("ε".equals(change)){
                    continue;
                }
                Set<String> retSet;
                if(chArrayList.contains("ε")){
                    retSet = CommonUtils.closure(CommonUtils.move(set, change, statusMap), statusMap);
                }else{
                    retSet = CommonUtils.move(set, change, statusMap);
                }
                if(retSet == null || retSet.size() == 0){ // 无状态
                    Set<String> set2 = new HashSet<>();
                    set2.add("^");
                    statusChanged.put(change, set2);
                }else{ //有状态
                    statusChanged.put(change, retSet);
                }
                //构建新的状态转换表
                newStatusMap.put(set, statusChanged);
                //如果不包含新得到的Set，且该新的到的Set不为空，则将其加入状态集中
                if(retSet != null && retSet.size() > 0 && !dStates.containsKey(retSet)){
                    dStates.put(retSet, false);
                }
//                CommonUtils.printMap("|LexMain:nfaToDfa():newStatusMap", newStatusMap);
            }
            dStates.put(set, true);
        }
//        CommonUtils.printMap("|LexMain:nfaToDfa():newStatusMap", newStatusMap);
        mapSimplify();
        return new StatusInfo(newStatusMapSimplify, newStartStatus, newEndStatus);
    }

    /**
     * 获取没有被标记的key
     * @return 返回value为false的key
     */
    private Set<String> getKey(){
        Set<String> key = null;
        // Map,HashMap并没有实现Iteratable接口.不能用于增强for循环.
        for(Set<String> getKey: dStates.keySet()){
            if(dStates.get(getKey).equals(false)){
                key = getKey;
            }
        }
        return key;
    }

    /**
     * 将状态转换表简化
     */
    private void mapSimplify(){
        statusMapTable = new HashMap<>();
        Set<Set<String>> newStatusKey = newStatusMap.keySet();
        newStartStatus = new ArrayList<>();
        newEndStatus = new ArrayList<>();
        // 构建状态映射
        // 确定初态
        int statusCode = 0;
        // 确定不可达状态
        Set<String> cannotArrive = new HashSet<>();
        cannotArrive.add("^");
        statusMapTable.put(cannotArrive, "^");
        for(Set<String> key : newStatusKey){
            if(!statusMapTable.containsKey(key)){
                statusMapTable.put(key, String.valueOf(statusCode++));
                // 重新确定初态
                for(String start : startStatus){
                    if(key.contains(start)){
                        newStartStatus.add(statusMapTable.get(key));
                        break;
                    }
                }
                // 重新确定终态
                for(String end : endStatus){
                    if(key.contains(end)){
                        newEndStatus.add(statusMapTable.get(key));
                        System.out.println("|NfaToDfa:mapSimplify(): currKey:" + key);
                        break;
                    }
                }
            }
        }
        System.out.println("|NfaToDfa:mapSimplify(): newStatusMap:" + newStatusMap);
        System.out.println("|NfaToDfa:mapSimplify(): statusMapTable:" + statusMapTable);
        System.out.println("|NfaToDfa:mapSimplify(): newStartStatus:" + newStartStatus);
        System.out.println("|NfaToDfa:mapSimplify(): newEndStatus:" + newEndStatus);
        // 重构状态转换表
        newStatusMapSimplify = new HashMap<>();
        Set<Set<String>> newStatusMapKey = newStatusMap.keySet();
        for(Set<String> keySet : newStatusMapKey){
            Map<String, String> changeStatus = new HashMap<>();
            for(String change : chList){
                if("ε".equals(change)){
                    continue;
                }
                Set<String> valueSet = newStatusMap.get(keySet).get(change);
                String keyStr = statusMapTable.get(keySet);
                String valueStr = statusMapTable.get(valueSet);
                changeStatus.put(change, valueStr);
                newStatusMapSimplify.put(keyStr, changeStatus);
            }
        }
        removeUselessStatus();
    }

    /**
     * 去除无用的节点：不可达，且该节点不可转换成其他节点
     */
    private void removeUselessStatus(){
        Set<String> statusKeySet = newStatusMapSimplify.keySet();
        Set<String> statusValueSet = new HashSet<>();
        // 获取状态转换表中的所有表项
        for(String statusKey : statusKeySet){
            for(String change : chArrayList){
                if("ε".equals(change)){
                    continue;
                }
                statusValueSet.add(newStatusMapSimplify.get(statusKey).get(change));
            }
        }
        Iterator<String> statusKeySetIterator = statusKeySet.iterator();
        while (statusKeySetIterator.hasNext()){
            String statusKey = statusKeySetIterator.next();
            // 不可达
            if( !statusValueSet.contains(statusKey)){
                boolean canGoto = false;
                for(String change : chArrayList){
                    if("ε".equals(change)){
                        continue;
                    }
                    if( !"^".equals(newStatusMapSimplify.get(statusKey).get(change)) ){
                        canGoto = true;
                        break;
                    }
                }
                // 没有指向任何新状态
                if( !canGoto ){
                    newStatusMapSimplify.remove(statusKey);
                    statusKeySet = newStatusMapSimplify.keySet();
                    statusKeySetIterator = statusKeySet.iterator();
                }
            }
        }
    }
}
